
    \begin{figure}[!tb]
    \begin{algorithmic}[1]
    \STATE \code{class Polygon<\underline{I extends ReadOnly}> \lb}
    \STATE \code{~~List<\underline{I},Point<\underline{I}>> points;}
    \STATE \code{~~\underline{\assignable} Point<\underline{I}> cachedHighestPoint;} \COMMENT{Illegal!}  \label{Polygon:cachedHighestPoint}
    \STATE \code{~~\underline{@ReadOnly} Point<\underline{I}> getHighestPoint() \lb} \label{Polygon:getHighestPoint:start}
    \STATE \code{~~~~if (cachedHighestPoint==null) \lb \ldots}
    \STATE \code{~~~~~~cachedHighestPoint = \ldots;}
    \STATE \code{~~~~\rb}
    \STATE \code{~~~~return cachedHighestPoint;}
    \STATE \code{~~\rb} \label{Polygon:getHighestPoint:end}
    \STATE \code{~~Point<\underline{Mutable}> loophole(Point<\underline{ReadOnly}> p) \lb} \label{Polygon:loophole:start}
    \STATE \code{~~~~Polygon\hgn{\underline{Mutable}} mutPoly = } \label{Polygon:mutPoly:start}
    \STATE \code{~~~~~~~~~~~~~~~~~~~~~new Polygon\hgn{\underline{Mutable}}();} \label{Polygon:mutPoly:end}
    \STATE \code{~~~~Polygon\hgn{\underline{ReadOnly}} roPoly = mutPoly;}
    \STATE \code{~~~~roPoly.cachedHighestPoint = p;} \label{Polygon:assign}
    \STATE \code{~~~~return mutPoly.cachedHighestPoint;} \label{Polygon:return}
    \STATE \code{~~\rb} \label{Polygon:loophole:end}
    \STATE \code{\rb}
    \end{algorithmic}
    \caption{Class \code{Polygon<\underline{I}>} with an (illegal) \emph{assignable \this-mutable} field in IGJ.
        Such fields are legal in OIGJ, if they are owned by \this. IGJ syntax is explained in \Ref{Section}{IGJ}.}
    \label{Figure:Polygon-IGJ}
    \end{figure}


\Ref{Figure}{Polygon-IGJ} shows a \emph{caching} example using a \code{Polygon} class in IGJ
        with an assignable \this-mutable field~\code{cachedHighestPoint} (line~\ref{Polygon:cachedHighestPoint}).
    Method \code{getHighestPoint} (lines~\ref{Polygon:getHighestPoint:start}--\ref{Polygon:getHighestPoint:end})
        caches and returns the polygon's center.

Method \code{loophole} (lines~\ref{Polygon:loophole:start}--\ref{Polygon:loophole:end})
        shows how to convert a readonly point~\code{p} to mutable.
    We first create a mutable polygon (lines~\ref{Polygon:mutPoly:start}--\ref{Polygon:mutPoly:end}),
        then convert it to readonly and assign \code{p} to \code{cachedHighestPoint} (line~\ref{Polygon:assign}).
    Field \code{cachedHighestPoint} is \this-mutable,
        thus, in a readonly polygon it is readonly (line~\ref{Polygon:assign})
        and in a mutable polygon it is mutable (line~\ref{Polygon:return}).
    The assignment on line~\ref{Polygon:assign} is legal,
        because field \code{cachedHighestPoint} is also assignable.
    The combination of the two concepts creates the loophole, and therefore fields like \code{cachedHighestPoint}
        are illegal in IGJ.



    OIGJ prevents the above \code{loophole} if
        \code{cached}-\code{Center} is owned by \this,
        because point~\code{p} is not owned by \this,
        and \code{cachedHighestPoint} may only be assigned by \this.

        




\begin{figure}[!tb]
\begin{algorithmic}[1]
\STATE \code{interface Visitor<O,I,\underline{NodeO,NodeI}> \lb} \label{Visitor:start}
%\STATE \code{~~\underline{NodeO extends World,NodeI extends ReadOnly}> \lb}
\STATE \code{~@Mutable void visit(Node<\underline{NodeO,NodeI}> n);} \label{Visitor:visit}
\STATE \code{\rb} \label{Visitor:end}
\STATE \code{class Node<\underline{O,I}> \lb}
\STATE \code{~@ReadOnly <VisitorO> void accept(} \label{Visitor:accept}
\STATE \code{~~~~~~~~~~~~Visitor<VisitorO,Mutable,\underline{O,I}> v) \lb}
\STATE \code{~~~v.visit(this)}
\STATE \code{~\rb}
\STATE \code{\rb}
\STATE \COMMENT{Visiting a readonly hierarchy.}
\STATE \code{Node<\underline{World,ReadOnly}> readonlyNode = \ldots;} \label{Visitor:match1:ReadOnly}
\STATE \code{readonlyNode.accept(}
\STATE \code{~new Visitor<This,Mutable,\underline{World,ReadOnly}>() \lb} \label{Visitor:match2:ReadOnly}
\STATE \code{~~@Mutable void visit(Node<\underline{World,ReadOnly}> n)\lb} \label{Visitor:visit:ReadOnly}
\STATE \code{~~~\ldots} \COMMENT{Can mutate the visitor, but not the nodes.}
\STATE \code{~~\rb}
\STATE \code{~\rb);}
\STATE \COMMENT{Visiting a mutable hierarchy.}
\STATE \code{Node<\underline{This,Mutable}> mutableNode = \ldots;} \label{Visitor:match1:Mutable}
\STATE \code{mutableNode.accept(}
\STATE \code{~new Visitor<This,Mutable,\underline{This,Mutable}>() \lb} \label{Visitor:match2:Mutable}
\STATE \code{~~@Mutable void visit(Node<\underline{This,Mutable}> n) \lb} \label{Visitor:visit:Mutable}
\STATE \code{~~~\ldots} \COMMENT{Can mutate the visitor and the nodes.} \label{Visitor:visit:Mutable:capture}
\STATE \code{~~\rb}
\STATE \code{~\rb);}
\end{algorithmic}
\caption{Visitor pattern in OIGJ. The \code{Node}'s ownership and immutability are underlined.}
\label{Figure:OIGJ-Visitor-pattern}
\end{figure}

\begin{lstlisting}
@AssignsFields
  LinkedList(Collection<? extends E> c) {
    header.next = header.previous = header;
}
@AssignsFields
  LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
@AssignsFields
  void addAll(Collection<? extends E> c) {
    // @PrivateI is the default; but we
    // write it anyway to make it clearer.
    @PrivateI Entry<E> successor = header;
    @PrivateI Entry<E> predecessor =
      successor.previous;
    for (E e : c) {
      @PrivateI Entry<E> e =
        new @PrivateI
          Entry<E>(e, successor, predecessor);
      predecessor.next = e;
      predecessor = e;
    }
    successor.previous = predecessor;
}
\end{lstlisting}



\begin{figure*}[!tb]
\begin{lstlisting}
// Implementation A: duplicating iterator code
class ListIterRW implements Iterator {
  peer List thelist;
  peer Entry cur;
  ...
}
class ListIterRO implements Iterator {
  readonly List thelist;
  readonly Entry cur;
  ...
}
class LinkedList {
  pure free ListIterRO getIteratorRO() {
    return new free ListIterRO(this);
  }
  pure peer ListIterRW getIteratorRW() {
    return new peer ListIterRW(this);
  }
  ...
}
// Implementation B: no duplication using casts
class ListIter implements Iterator {
  readonly List thelist;
  readonly Entry cur;
  public void remove() {
    ((peer List) thelist).remove((peer Entry)cur);
  }
  ...
}
class LinkedList {
  pure free ListIter getIterator() {
    return new free ListIter(this);
  }
  ...
}
\end{lstlisting}
\caption{\code{LinkedList} iterators in GUT.}
\label{Figure:GUT-LinkedList}
\end{figure*}

you can express in OGJ
    ``\emph{my} collection of \emph{library} books"
    and in IGJ
    a ``\emph{mutable} collection of \emph{immutable} books".
    and in OIGJ
    ``\emph{my mutable} collection of \emph{library immutable} books".

IGJ %~\cite{zibin:2007:immutability}
        did not have an explicit non-transitive rule.
    Instead, it revised the Field-assignment and Method-invocation rules to prevent transitivity in case of \AssignsFields,
        i.e., it required that the receiver \code{o} must be \this in case of \AssignsFields.
    To make it easier to present OIGJ, we choose to use an explicit non-transitive rule;
        it also made Field-assignment and Method-invocation rules simpler.


Ownership Generic Java (OGJ)~\cite{PotaninNCB2006}
    and Immutability Generic Java (IGJ)~\cite{zibin:2007:immutability}
    are language extensions of \Java{}
    that can express ownership and immutability information
    without changing \Java{}'s syntax;
    a new type parameter is added to all types (at the beginning of the list of
    type parameters).
E.g., you can express in OGJ
    ``\emph{my} collection of \emph{public} books"
    as follows
\begin{algorithmic}
\STATE \code{Collection\hgn{\underline{\This},Book\hgn{\underline{\World}}}},
\end{algorithmic}
    in IGJ
    a ``\emph{mutable} collection of \emph{immutable} books"
    is
\begin{algorithmic}
\STATE \code{Collection\hgn{\underline{\Mutable},Book\hgn{\underline{\Immutable}}}}.
\end{algorithmic}

This paper presents \emph{OIGJ},
    a language combining ownership and immutability, e.g.,
    in OIGJ
    ``\emph{my mutable} collection of \emph{public immutable} books"
    is represented as
\begin{algorithmic}
\STATE \code{Collection\hgn{\underline{\This},\underline{\Mutable},Book\hgn{\underline{\World},\underline{\Immutable}}}}.
\end{algorithmic}

,
    e.g., using annotations the above type is
\begin{algorithmic}
\STATE \code{\PrivateMutable Collection\hgn{\immutableAnnot Book}}.
\end{algorithmic}
    % an annotation processor



    // Examples of bad code that is prevented by OIGJ
    @M void merge(LinkedList<Mutable,O,E> l) {
        this.header = l.header; // illegal because  l.head  is RO due to field access rule
        this.header.next = l.header; // illegal (as above)
    }




About ownership nesting:
The algorithm is pretty complex (build constraints on all variables, check the constraints on instantiation).
But it should have been discussed in OGJ, so I won't discuss it here.
Example:
class A<O,O2> {
  List<This,O> l1; // O <= This
  List<O,O2> l2; // O <= O2
}

Give example with generic method, discuss implementation using constraints on variables.
\begin{lstlisting}
<O extends World> void foo(Point<O> p) {
  List<This, Point<O>> l; ...
}
\end{lstlisting}
In a method with generic owner parameter,
    you cannot create anonymous classes that depend on
    the owner parameter.
(Because then it is possible to capture an owned object on the heap.)
